package com.sushi.bigblog.utils;

import java.util.HashMap;
import java.util.Map;

/**
 * User: bianpeng
 * Date: 11-12-6
 */
public class LRUCache <K, V> {
    private Map<K, Entry<K, V>> map = new HashMap<K, Entry<K, V>>();
    private int limit;
    private int size = 0;

    private static class Entry <K, V> {
        K key;
        V val;

        Entry<K, V> prev;
        Entry<K, V> next;
        int hits;
    }

    private Entry<K, V> head;
    private Entry<K, V> tail;

    public LRUCache(int limit) {
        this.limit = limit;
    }

    public void put(K key, V val) {
        Entry<K, V> exists = map.get(key);
        if (exists != null) {
            exists.val = val;
            return;
        }
        expireOverEntries();
        exists = new Entry<K, V>();
        exists.key = key;
        exists.val = val;
        map.put(key, exists);

        ++size;

        if (tail == null) {
            tail = exists;
        }
        if (head == null) {
            head = exists;
        } else {
            exists.next = head;
            head.prev = exists;
            head = exists;
        }
    }

    /**
     * 把过期的挤出去
     */
    private void expireOverEntries() {
        while (size > limit && tail != null) {
            assert tail.prev != null;
            tail = tail.prev;
            tail.next = null;
            --size;
        }
    }

    public V get(K key) {
        Entry<K, V> exists = map.get(key);
        if (exists == null) return null;

        ++exists.hits;
        if (exists.prev != null) {
            exists.prev.next = exists.next;
            exists.prev = null;
            exists.next = head;
            head.prev = exists;
            head = exists;
        }
        return exists.val;
    }
}
